UVa/11485 - Extreme Discrete Summation/eds.cpp

   1 //Robado de http://acm.uva.es/board/viewtopic.php?f=42&t=42314&sid=0cfc4d6e55802e83ea57fed814183ab6
   2 #include<stdio.h>
   3 #include<string.h>
   4
   5 #define SZ 105
   6
   7 long long dp[10][SZ] , ret , cnt[SZ];
   8
   9 int main(){
  10    //freopen("e.in" , "r" , stdin);
  11    //freopen("e.out" , "w" , stdout);
  12    long long n , i , x , j , sm;
  13    double p;
  14    while(scanf("%lld" , &n) == 1 && n){
  15       memset(cnt , 0 , sizeof(cnt));
  16       sm = 75;
  17       for(i = 0;i<n;i++){
  18          scanf("%lf" , &p);
  19          x = (long long)(p*10 + .5);
  20          cnt[i] = x%10;
  21       }
  22       ret = 0;
  23       memset(dp , 0 , sizeof(dp));
  24       for(i = 0;i<n;i++)
  25          dp[0][cnt[i]] ++;
  26       for(i = 1;i<7;i++)
  27          for(j = 0;j<n;j++)
  28             for(x = sm;x>=cnt[j];x--)
  29                dp[i][x] += dp[i-1][x-cnt[j]];
  30       for(i = 0;i<n;i++){
  31          for(j = 0;j<=sm;j++)
  32             if(dp[6][j])
  33                ret += (((j+cnt[i])/10)*dp[6][j]);
  34       }
  35       printf("%lld\n" , ret);
  36    }
  37    return 0;
  38 }